package com.wdc.recursion;

//实现插入排序的递归算法

import java.util.Arrays;

public class E05InsertionSort {
    public static void main(String[] args) {
        int[] a = {2 ,4 , 8, 10,7,1};
        sort(a);
        System.out.println(Arrays.toString(a));
    }


    public static void sort(int[] a){
       // insertion(a,1);
        insertion2(a,1);
    }

    /**
     * 插入排序 递归实现 不使用交换元素的方式
     * @param a 待排序数组
     * @param low 待排序的左边界
     */
    private static void insertion(int[] a,int low){
        if (low == a.length){
            return;
        }

        int t = a[low];
        int i = low -1;  //已经排序的右边界指针

        while (i >= 0 && a[i] > t){ //没有找到插入位置，就让 a[i] 元素向后移动一位空出待插入的位置
            a[i + 1] = a[i];  //空出插入位置
            i--;

        }


        //找到插入循环
        if ( i + 1 != low) a[i + 1] =t;


        insertion(a,low+1);
    }

    /**
     * 使用了交换元素的算法  但效率没有第一个高
     * @param a
     * @param low
     */
    private static void insertion2(int[] a ,int low){
        if (low == a.length){
            return;
        }

        int i = low -1;
        while( i >= 0 && a[i] > a[i + 1]){
            int temp = a[i];
            a[i] = a[low];
            a[low] = temp;
            i --;
        }

        insertion(a,low+1);
    }


}
